# -*- coding: utf-8 -*-

"""646. 最长数对链
给你一个由 n 个数对组成的数对数组 pairs ，其中 pairs[i] = [lefti, righti] 且 lefti < righti 。
现在，我们定义一种 跟随 关系，当且仅当 b < c 时，数对 p2 = [c, d] 才可以跟在 p1 = [a, b] 后面。我们用这种形式来构造 数对链 。
找出并返回能够形成的 最长数对链的长度 。
你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例 1：
输入：pairs = [[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4] 。

示例 2：
输入：pairs = [[1,2],[7,8],[4,5]]
输出：3
解释：最长的数对链是 [1,2] -> [4,5] -> [7,8] 。

提示：
n == pairs.length
1 <= n <= 1000
-1000 <= lefti < righti <= 1000"""

from random import randint

class Solution:
    """
    这种最长子序列的问题都可以转化成最大增长序列的问题，关键就看怎么排序。
    如果 [a,b] R跟随 [c,d] 等价于 b < c, 则在有序序列中 [a,b] 一定排在 [c,d] 之前。所以可以先按 order by elem[0] asc, elem[1] asc。
    只需要抽取里面的跟随关系[a  b]  [c  d]，至于 [a  (c  b]  d), (c  [a  b]  d) 这种不满足跟随关系的不用介意先后。但是一定要保证满足跟随关系的一定有先后。
    定义 f(i) 为计算以有序序列 i 元素为尾部的最长增长子序列长度。
    递归定义：
        f(i) = max(f(j)+1, f(i))        # 0 < j < i 且 elemJ[1] < elemI[1]
    递归基础：
        f(i) = 1                        # 任意位置的初始增长子序列长度为 1
    将递归计算过程转化为以状态转移的递推过程。
    """
    def findLongestChain(self, pairs: list) -> int:
        pairs = list(set([tuple(elem) for elem in pairs]))
        Solution.quick_sort(pairs)
        size = len(pairs)
        dp = [1 for _ in range(size)]
        i = 1
        while i < size:
            j = 0
            while j < i:
                if Solution.follow(pairs[j], pairs[i]):
                    dp[i] = max(dp[j]+1, dp[i])
                j += 1
            i += 1
        return max(dp)

    @staticmethod
    def quick_sort(pairs):
        def do(m, n):
            i, j, pivot = m, n, pairs[randint(m, n)]
            while True:
                while i < j and Solution.lt(pairs[i], pivot):
                    i += 1
                while i < j and Solution.gt(pairs[j], pivot):
                    j -= 1
                if i >= j:
                    p = i
                    break
                else:
                    pairs[i], pairs[j] = pairs[j], pairs[i]

            if m < p-1:
                do(m, p-1)
            if n > p+1:
                do(p+1, n)

        do(0, len(pairs)-1)

    @staticmethod
    def lt(elemA, elemB):
        if elemA[0] < elemB[0]:
            return True
        elif elemA[0] == elemB[0] and elemA[1] > elemB[1]:
            return True
        else:
            return False

    @staticmethod
    def gt(elemA, elemB):
        if elemA[0] > elemB[0]:
            return True
        elif elemA[0] == elemB[0] and elemA[1] < elemB[1]:
            return True
        else:
            return False

    @staticmethod
    def follow(elemA, elemB):
        return elemA[1] < elemB[0]

if __name__ == '__main__':
    rs = Solution().findLongestChain([[1,2], [2,3], [3,4]])
    print(rs)
